\section{Our technique}

A \sicl{} object is either an \emph{immediate object} or a \emph{heap
  object}.  A heap object is either a \texttt{cons} cell or a
\emph{general instance}.%
\footnote{Since heap allocated objects are either \texttt{cons} cells
  or general instances, it follows that general instances are used to
  represent not only \emph{standard objects}, but also structure
  instances, instances of built-in classes such as \texttt{symbol} and
  \texttt{package}, arrays, bignums, complex numbers, etc.}
General instances and \texttt{cons} cells have
distinct unique \emph{tags}.  Every general instance is represented by
its \emph{header}.  The header contains two pointers, one to the
\emph{class} of the instance and one to the \emph{rack} of the
instance.  The pointer to the class is a tagged pointer to another
general instance.  The pointer to the rack is a raw machine pointer.
This representation is shown in \refFig{fig-general-instance}.

\begin{figure}
\begin{center}
\inputfig{fig-general-instance.pdf_t}
\end{center}
\caption{\label{fig-general-instance}
Representation of a general instance.}
\end{figure}

Each class is assigned a \emph{unique number} starting at $0$.  The
number is assigned when the class is finalized, and a new number is
assigned whenever a class is finalized as a result of changes to the
class or any of its superclasses.  Currently, class numbers are never
reused.  This way of allocating class numbers is advantageous because
it often results in a subtree of classes occupying a \emph{dense
  interval} of class numbers, the importance of which is discussed
below.  On a $64$-bit architecture with $63$-bit or $62$-bit fixnums,
the unique number will always be a fixnum.  On $32$-bit architectures
this is very likely also true, and it is certainly true if class
numbers are reused.%
\footnote{The garbage collector would have to take care of recycling
  class numbers.}  If class numbers are not reused, on a $32$-bit
platform one might have to use two words in order to be on the safe
side.

The first element of the rack of every general instance is called the
\emph{stamp}.  The stamp is the unique number of the class as it was
when the instance was created or updated as a result of changes to its
class.  An instance is \emph{obsolete} if and only if its stamp is not
the same as the unique number of its class.

Together, the unique number of the class and the stamp of the instance
play a role similar to that of the \emph{class wrapper} of PCL.  The
unique number of the class corresponds to the most recent wrapper for
the class and the stamp corresponds to a wrapper that may have become
obsolete as a result of updates to the class.  

Our dispatch technique works by comparing the stamp of each
specialized argument to a set of non-negative constant integers in a
way similar to a binary search.  The result of these comparisons
identifies the argument as being an instance of a particular class, or
of one of a set of classes for which the same effective method is
valid.  As an example, let us take a generic function that specializes
on a single argument, and that has already been called with classes
numbered 1, 4, 5, 6, 8, and 10, where classes numbered 4, 5, and 6
result in the same effective method being invoked.  The discriminating
function of this generic function would then look like this:

\begin{verbatim}
(tagbody 
    (if (< stamp 7)
        (if (< stamp 4)
            (if (= stamp 1)
                (go m1)
                (go miss))
            (go m2))
        (if (= stamp 8)
            (go m3)
            (if (= stamp 10)
                (go m4)
                (go miss))))
  m1
    ;; invoke method for class numbered 1
     ...
    (go out)
  m2
    ;; invoke method for classes numbered 4, 5, 6
     ...
    (go out)
  m3
    ;; invoke method for class numbered 8
     ...
    (go out)   
  m4
    ;; invoke method for class numbered 10
     ...
    (go out)   
  miss
    ;; handle miss
    ...
  out)
\end{verbatim}

This discriminating function is generated from the \emph{call history}
of the generic function.  The call history is a simple list of
entries, where each entry contains a list of classes for each
specialized parameter and a corresponding effective method to call. 

As can be seen from this example, in this case, a maximum of
three tests will be performed for six different classes.  The number
of tests required is logarithmic in the number of entries of the call
history.

The advantage of this technique is that on modern processors,
comparing integers is very fast, whereas table lookups require memory
accesses which are significantly more costly in general.

In terms of different types of operations, our technique
requires the following steps for a simple slot reader:

\begin{enumerate}
\item Access the rack of the argument; a memory access.
\item Access the stamp of the rack; a memory access.
\item Compare the stamps to a set of constants; fast register
  operations.
\item The slot containing the desired object is read and returned; a
  memory access.
\end{enumerate}

As we can see, only 3 memory accesses are required.  The number of
comparisons is not constant, of course, but it is very small for the
vast majority of generic functions, and quite reasonable (compared to
the cost of a memory access) even when a very large number of cases
needs to be handled.

Like the technique used by PCL, our technique automatically detects
obsolete instances.  When a class is updated, every generic function
that dispatches on this class%
\footnote{The function
  \texttt{specializer-direct-generic-functions} returns a list of
  generic functions that have a method using the class as a specializer.}
is determined, and the \emph{call history} of each such generic
function is searched for entries using the class.  These entries are
removed, and then the discriminating function is either recomputed from
the call history, or is set to a function that, when invoked,
recomputes the discriminating function from the call history.   The
result is that, if an obsolete instance is used in dispatch, its stamp
will not be valid for dispatch, so the discriminating function will
fail to recognize the instance, forcing an update of the instance and
a new dispatch attempt. 

In contrast to the technique used by PCL, our technique makes it more
costly to update classes.  In PCL, invalidating a class wrapper is a
simple matter of setting the hash seed to $0$.  Our technique requires
that the call history be updated and the discriminating function be
recomputed for every generic function with a method that specializes
on the class being updated.  While this cost is unbounded, it is
acceptable in practice. 

While not directly related to dispatch performance, an important
consequence of the split between the header and the rack for every
general instance is that generic functions can be updated without
requiring locking, by using a simple version of software transactional
memory.  When a generic function needs to be updated (for instance as
a result of one of the classes it specializes on being updated), the
rack and the call history can be copied, and then modifications can be
made to the copy, and finally, the copied rack can replace the
original rack by the use of a \texttt{compare-and-swap} instruction.
Should the instruction fail, the attempted update is restarted. 

